package tree;

public class Heap<T extends Comparable<T>> {
    //存储堆中的元素个数
    private int N;
    //记录堆中的元素
    private T[] data;
    private static int capacity = 10;
    public Heap(){
        //初始化元素个数
        this.N=0;
        //初始化数组长度
        //noinspection unchecked
        this.data = (T[]) new Comparable[capacity];
    }
    public int getN(){
        return this.N;
    }
    //删除堆中最大的元素，并返回这个最大元素
    public T delMax(){
        //返回被删除的元素
        T t = data[1];
        //判断是否为空
        if (this.N<1){
            System.out.println("没有元素插入");
            return null;
        }
        //判断数组是否只有一个元素
        if (this.N==1){
            data[1]=null;
        }
        //交换第一个和最后一个元素的位置
        data[1]=data[this.N];
        data[this.N--]=null;
       sink(1);
        return t;
    }
    //不需要0位置的索引
    public void insert(T t){
//        for (int i = 1; i < this.N; i++) {
//            if (data[i].equals(t)){
//                return;
//            }
//        }
        if (this.N+1>=data.length){
            //noinspection unchecked
            T[] newData =(T[]) new Comparable[(int) (data.length*1.5)];
            for (int i = 0; i < data.length; i++) {
                newData[i]=data[i];
            }
            data=newData;
        }

        data[++this.N] = t;
        swim(N);
    }
    private void swim(int k){
        while (k>1) {
            if (!less(k,k/2)){
                exchange(k,k/2);
            }
            k=k/2;
        }
    }
    //元素下沉
    private void sink(int k){
        //判断下沉元素是否小于元素个数
        while (k<=this.N) {
            if (k*2+1>this.N){
                break;
            }
            if (k*2==this.N){
                int next = 2*k;
                if (less(k,next)){
                    exchange(k,next);
                }
                k=next;
            }else {
            int next =  less(k*2+1,k*2)?k*2:k*2+1;
            if (less(k,next)){
                exchange(k,next);
                }
                k=next;
            }
        }

    }
    //判断索引i处的元素是否小于j处的元素
    private boolean less(int i,int j){
        return data[i].compareTo(data[j])<0;
    }
    private void exchange(int i ,int x){
        T t = data[i];
        data[i] = data[x];
        data[x] = t;
    }
}
